// lk15. [剪枝] 三数之和 a + b + c = 0
// https://leetcode.cn/problems/3sum/
//给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，
//使得 a + b + c = 0 请你找出所有和为 0 且不重复的三元组。
//注意：答案中不可以包含重复的三元组。
//输入：nums = [-1,0,1,2,-1,-4]
//输出：[[-1,-1,2],[-1,0,1]]
//输入：nums = []
//输出：[]
//输入：nums = [0]
//输出：[]

#include <bits/stdc++.h>
using namespace std;

#define DEBUG_
#ifdef DEBUG_
#define PF(...) printf(__VA_ARGS__)
#define FRE(x) freopen("d:/oj/" #x ".in", "r", stdin)
#define FREC fclose(stdin), fclose(stdout);
#else
#define PF(...)
#define FRE(x)
#define FREC
#endif
class Solution {
public:
  vector<vector<int>> threeSum(vector<int> nums) {
    vector<vector<int> > ans;
    sort(nums.begin(), nums.end());
    for (size_t i=0; i<nums.size(); i++) {
      if (i>0 && nums[i-1] == nums[i]) {
        continue;
      }
      size_t k=nums.size()-1;
      for (size_t j=i+1; j<nums.size();j++) {
        if (j>i+1 && nums[j-1] == nums[j]) {
          continue;
        }
        for (; k>j && nums[i]+nums[j]+nums[k] > 0;) {
		  k--;
        }
        if (k == j) {
          break;
        }
        if (nums[i]+nums[j]+nums[k]==0){
          ans.push_back({nums[i],nums[j],nums[k]});
        }
      }
    }
    return ans;
  }
};

int main_3sum() {
  Solution sol;
  vector<vector<int>> out = sol.threeSum({-1, 0, 1, 2, -1, -4});
  for (auto vt : out)
  for (auto nn : vt) PF("%d,", nn);
  PF("\n");
  return 0;
}
